package com.kyle.java.Array;

import java.lang.reflect.Array;

public class sparseArray {

    public static void main(String[] args) {
        int[][] array = {{0, 0, 1}, {0, 3, 2}, {0, 3, 3}};
        System.out.println("原始数组：");
        printArray(array);
        System.out.println("\n稀疏数组：");
        printArray(compressArray(array, 3, 3));
    }

    public static void printArray(int[][] array) {
        for (int a = 0; a < array.length; a++) {
            System.out.println();
            for (int b = 0; b < array[0].length; b++) {
                System.out.print(array[a][b]);
                System.out.print(" ");
            }
        }
    }

    //创建稀疏数组
    public static int[][] compressArray(int[][] array, int i, int j) {
        int numOfElem = 0; //原始数组元素个数
        //遍历原始数组得到元素个数
        for (int a = 0; a < i; a++) {
            for (int b = 0; b < j; b++) {
                if (array[a][b] != 0) {
                    numOfElem++;
                }
            }
        }
        //创建稀疏数组
        int[][] compressedArray = new int[numOfElem + 1][3];
        //稀疏数组第一个值记录的是 元素数组的 行数、列数、元素数
        compressedArray[0][0] = i;
        compressedArray[0][1] = j;
        compressedArray[0][2] = numOfElem;

        //将压缩数组的第一个元素
        //遍历原始数组 将元素写入到压缩数组中的第 insert位置中
        int insert = 1;

        for (int a = 0; a < i; a++) {
            for (int b = 0; b < j; b++) {
                if (array[a][b] != 0) {
                    // 将非0元素写入到压缩数组中
                    compressedArray[insert][0] = a;
                    compressedArray[insert][1] = b;
                    compressedArray[insert][2] = array[a][b];
                    insert++;
                }
            }
        }

        return compressedArray;
    }


}
